#include <stdlib.h>
#include <stdio.h>

typedef int ElemType;
typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

//头插法
void Init_head_LinkList(LinkList &L) {
    L = (LinkList) malloc(sizeof(LNode));
    ElemType data;
    LinkList q = L, p;
    q->next = NULL;
    scanf("%d", &data);
    while (data != 9999) {
        p = (LinkList) malloc(sizeof(LNode));
        p->data = data;
        p->next = q->next;
        q->next = p;
        scanf("%d", &data);
    }
}

//尾插法
void Init_tail_LinkList(LinkList &L) {
    L = (LinkList) malloc(sizeof(LNode));
    ElemType data;
    LinkList p, q = L;
    scanf("%d", &data);
    while (data != 9999) {
        p = (LinkList) malloc(sizeof(LNode));
        p->data = data;
        q->next = p;
        q = p;
        scanf("%d", &data);

    }
    p->next = NULL;
}


void arrayPrint_LinkList(LinkList L) {
    L = L->next;
    while (L) {
        printf("%2d ", L->data);
        L = L->next;
    }
    printf("\n");
}

//3.设L为带头节点的单链表，编写算法实现从尾到头反向输出每个结点的值。
//递归思想
void Reverse_Print(LinkList L) {
    if (L->next != NULL) {
        Reverse_Print(L->next);
    }
    if (L != NULL) {
        printf("%2d ", L->data);
    }
}
void R_Ignore_Head(LinkList L) {
    if (L->next!=NULL) Reverse_Print(L->next);
}

int main() {
    /**第三题*/
    LinkList L;
    //尾插法建立链表
    Init_tail_LinkList(L);
    arrayPrint_LinkList(L);
    //实现从尾到头反向输出每个结点的值。
    R_Ignore_Head(L);
    return 0;
}
